package DulLinkedList;

/**
 * created with IDEA
 * 双向链表
 * 单链表只有一个指向下一结点的指针，也就是只能next
 * 双链表除了有一个指向下一结点的指针外，还有一个指向前一结点的指针，可以通过prev()快速找到前一结点
 *
 * 1、删除单链表中的某个结点时，一定要得到待删除结点的前驱，得到该前驱有两种方法，第一种方法是在定位待删除结点的同时一路保存当前结点的前驱。
 * 第二种方法是在定位到待删除结点之后，重新从单链表表头开始来定位前驱。尽管通常会采用方法一。但其实这两种方法的效率是一样的，指针的总的移动操作都会有2*i次。
 * 而如果用双向链表，则不需要定位前驱结点。因此指针总的移动操作为i次。
 *
 * 2、查找时也一样，我们可以借用二分法的思路，从head（首节点）向后查找操作和last（尾节点）向前查找操作同步进行，这样双链表的效率可以提高一倍。
 *
 * 可是为什么市场上单链表的使用多余双链表呢？
 *
 * 从存储结构来看，每个双链表的节点要比单链表的节点多一个指针，而长度为n就需要 n*length（这个指针的length在32位系统中是4字节，在64位系统中是8个字节）
 * 的空间，这在一些追求时间效率不高应用下并不适应，因为它占用空间大于单链表所占用的空间；这时设计者就会采用以时间换空间的做法，这时一种工程总体上的衡量。
 *
 * 循环双链表：
 * 循环双链表的构造源自双链表，即将终端结点的next指针指向链表中第一个结点，将链表中第一个结点的prior指针指向终端结点。
 * 带头结点的循环双链表当head->next和heaad->prior两个指针都等于head时链表为空。
 * 不带头结点的循环双链表当head等于null的时候为空。
 * 循环链表的算法操作：
 * 循环单链表和循环双链表由对应的单链表和双链表改造而来，只需在终端结点和头结点间建立联系即可。
 * 循环单链表终端结点的next结点指针指向表头结点；循环双链表终端结点的next指针指向表头结点，头结点的prior指针指向表尾结点
 *
 * https://www.cnblogs.com/ChenD/p/7814906.html
 *
 * @author haifeng.wang
 * @since 2019-06-19-16:25
 */
public class DulLinkedList<E> {

    //头节点
    private DulNode<E> head;
    //节点个数
    private int size;

    /**
     * 头结点不存储值 并且头结点初始化时 就一个头结点。
     * 所以头结点的前后节点都是自己
     * 并且这个链表的长度为0；
     */
    public DulLinkedList(){
        head = new DulNode<E>(null, null, null);
        head.prev = head.next;
        head = head.next;
        size = 0;
    }

    public int getSize(){
        return this.size;
    }

    public boolean isEmplty(){
        return size == 0;
    }

    /**
     * 判断索引是否超出范围
     */
    public void checkIndex(int index){
        if(index<0||index>=size){
            throw new IndexOutOfBoundsException();
        }
        return;
    }

    /**
     * 通过索引获取链表当中的节点
     *
     */
    public DulNode<E> getNode(int index){
        /**
         * 检查该索引是否超出范围
         */
        checkIndex(index);
        /**
         * 当索引的值小于该链表长度的一半时，那么从链表的头结点开始向后找是最快的
         */
        if(index<size/2){
            DulNode<E> cur = head.next;
            for(int i=0;i<index;i++){
                cur = cur.next;
            }
            return cur;
        }
        /**
         * 当索引值位于链表的后半段时，则从链表的另端开始找是最快的
         */
        /**
         * 此
         */
        DulNode<E> cur = head.prev;
        int newIndex = size - (index+1);
        for(int i=0;i<newIndex;i++){
            cur = cur.prev;
        }
        return cur;
    }

    /**
     * 获取节点当中的值
     */
    public E getValue(DulNode<E> cur){
        return cur.data;
    }

    /**
     * 获取第一个节点的值
     */
    public E getFirst(){
        return getValue(getNode(0));
    }

    /**
     * 获取最后一个节点的值
     */
    public E getLast(){
        return getValue(getNode(size-1));
    }

    /**
     * 插入节点
     */
    public void inesert(int index,E value){
        //如果这次插入时 链表是空的
        if(index==0){
            //这个节点的
            DulNode<E> cur = new DulNode<E>(head, head.next,value);
            head.next.prev = cur;
            head.next = cur;
            size++;
            return;
        }
        /**
         * 先根据给出的插入位置 找到该链表原来在此位置的节点
         */
        DulNode<E> node = getNode(index);
        /**
         *放置的位置的前一个节点就是原节点的前置节点 而后节点就是原节点
         */
        DulNode<E> cur = new DulNode<E>(node.prev,node,value);
        /**
         * 现将该位置也就是 原节点的前节点的后节点 赋值成为新节点
         * 然后将新节点的后置节点的值赋值成为原节点
         */
        node.prev.next = cur;
        node.prev = cur;
        size++;
    }
    /**
     * 向表头插入数据
     */
    public void insertTo(E Value)
    {
        inesert(0,Value);
    }
    /**
     * 将元素插入到链表的尾部
     */
    public void insertTotatil(E vlaue){
        DulNode<E> cur = new DulNode<E>(head.prev, head,vlaue);
        //head.prev 代表原来的尾部节点
        //遵循两个原则 一 新插入节点的前一个节点的后一个节点为新节点。新节点的后一个节点的前一个节点是新节点
        head.prev.next = cur;
        head.prev = cur;
        size++;
    }
    /**
     * 删除节点的方法
     */
    public void del(int index){
        checkIndex(index);
        DulNode<E> cur = getNode(index);
        //记住此时的指针还没断开 赋值以后才相当于断开
        cur.prev.next = cur.next;
        cur.next.prev = cur.prev;
        size--;
        cur = null;
        return;
    }
    /**
     * 删除第一个节点
     */
    public void  delFirst(){
        del(0);
    }
    /**
     * 删除最后一个节点
     */
    public void delLast(){
        del(size-1);
    }
}

